package com.leetcode.algorithm.y22.m08.w2;

/**
 * 79. 单词搜索
 * 
 * https://leetcode.cn/problems/word-search/
 * 
 * @author jie.deng
 *
 */
class Question0079Solution01 {

	public boolean exist(char[][] board, String word) {
		int rows = board.length;
		int cols = board[0].length;
		if (word.length() > rows * cols) {
			return false;
		}
		boolean[][] visited = new boolean[rows][cols];
		return backtracking(board, word, new int[] { -1, -1 }, visited, 0);
	}

	private boolean backtracking(char[][] board, String word, int[] prevPos, boolean[][] visited, int beginIdx) {
		if (beginIdx == word.length()) {
			return true;
		}
		char targetCh = word.charAt(beginIdx);
		int rows = board.length;
		int cols = board[0].length;
		if (beginIdx == 0) {
			for (int row = 0; row < rows; row++) {
				for (int col = 0; col < cols; col++) {
					if (board[row][col] == targetCh) {
						visited[row][col] = true;
						boolean flag = backtracking(board, word, new int[] { row, col }, visited, beginIdx + 1);
						if (flag) {
							return true;
						}
						visited[row][col] = false;
					}
				}
			}
		} else {
			int[][] dirs = new int[][] { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
			for (int[] dir : dirs) {
				int row = prevPos[0] + dir[0];
				int col = prevPos[1] + dir[1];
				if (row >= 0 && row < rows && col >= 0 && col < cols) {
					if (!visited[row][col] && board[row][col] == targetCh) {
						visited[row][col] = true;
						boolean flag = backtracking(board, word, new int[] { row, col }, visited, beginIdx + 1);
						if (flag) {
							return true;
						}
						visited[row][col] = false;
					}
				}
			}
		}
		return false;
	}

}